package com.skh.array;

import java.util.Arrays;

/*
相邻最大差值
 */
public class FindMaxDivision {

    /**
     * 题目描述
     * 请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。
     * <p>
     * 给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。
     * <p>
     * 测试样例：
     * [9,3,1,10],4
     * 返回：6
     */

    /*
    思路:
    1.数组排序
    2.用一个变量记录最大值
    3.遍历数组
     */
    public int findMaxDivision(int[] A, int n) {
        Arrays.sort(A);
        int max = 0;
        for (int i = 0; i < A.length - 1; i++) {
            int temp = A[i + 1] - A[i];
            if (temp > max) {
                max = temp;
            }
        }

        return max;
    }

    /**
     * 桶排序
     * 1.找出数组中的最大值和最小值。
     * 2.生成一个最大值-最小值的区间 比如最大值9，最小值3，那就需要7个桶 最大值-最小值+1
     * 3.往里面填  tong[A[i]-min]++
     * 4.查找空桶:计算这个数组中连续为0的最大间隔,最多的即为最大差值。
     * <p>
     * 例如：A={9,3,1,10},求出最大值为10，最小值为1，即可建立一个10 - 1 + 1 = 10 这么大的数组temp[10],
     * <p>
     * 因为A[]数组中的数的范围都在1~10之间，那我们可以在temp[0]=1,temp[2]=1,temp[8]=1,temp[9]=1，即
     * <p>
     * {1,0,1,0,0,0,0,0,1,1}，这最大差值即为temp[2]到temp[8]的距离6，返回6;
     */

    public int findMaxDivision2(int[] A, int n) {
        //找出数组中最大值和最小值
        int max = A[0];
        int min = A[0];
        for (int i = 0; i < n; i++) {
            if (A[i] > max) {
                max = A[i];
            }
            if (A[i] < min) {
                min = A[i];
            }
        }

        System.out.println("min = " + min);
        System.out.println("max = " + max);

        //创建桶
        int[] tong = new int[max-min+1];

        //填桶
        for (int i = 0; i < n; i++) {
            tong[A[i]-min]++;
        }
        System.out.println(Arrays.toString(tong));

        //查找空桶
        int curCount = 0; //当前空桶的数量
        int maxCount = 0; //最大空桶的数量
        for (int i = 0; i < tong.length; i++) {
            if (tong[i] == 0) {
                curCount++;
            } else {
                if (curCount > maxCount) {
                    maxCount = curCount;
                }
                curCount = 0;
            }
        }

        return maxCount+1; //如最大值为9，最小值为3，中间有5个空桶，但差值应为6
    }

}
